package demo.practice.linklist;

import demo.practice.ListNode;

public class P148 {


    public ListNode sortList(ListNode head) {
        if (head == null)
            return null;
        ListNode shead = new ListNode(head.val);
        ListNode cur = head.next;

        while (cur != null) {
            //int v = cur.val;
            if (cur.val <= shead.val) {
                //比当前头节点还小，则重置头节点
                ListNode nshead = new ListNode(cur.val);
                nshead.next = shead;
                shead = nshead;
            } else {
                ListNode scur = shead;
                while (scur.next != null && scur.next.val < cur.val) {
                    //当前节点 大于插入节点，则
                    scur = scur.next;
                }
                //当前节点的下一个节点大于等于插入值了，就插入了
                ListNode n = new ListNode(cur.val);
                n.next = scur.next;
                scur.next = n;
            }
            cur = cur.next;
        }
        return shead;
    }
}
